package com.ssh;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class FourSum_18 {
	public List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for (int j = 0; j < nums.length-3; j++) {
			if (j == 0 || nums[j] != nums[j-1]) {
				for (int i = j+1; i < nums.length-2; i++) {
					if ((i == j+1) || (nums[i] != nums[i-1])) {
						int lo = i+1,hi = nums.length-1,sum = target-nums[i]-nums[j];
						while (lo < hi) {
							if (nums[lo] + nums[hi] == sum) {
								list.add(Arrays.asList(nums[j], nums[i], nums[lo], nums[hi]));
								while (lo < hi && nums[lo] == nums[lo+1]) {
									lo++;
								}
								while (lo < hi && nums[hi] == nums[hi-1]) {
									hi--;
								}
								lo++;hi--;
							}else if (nums[lo] + nums[hi] < sum) {
								lo++;
							}else {
								hi--;
							}
						}
					}
				}
			}
		}
		return list;
    }
	
	@Test
	public void test () {
		int[] nums = {1, 0, -1, 0, -2, 2};
		System.out.println(fourSum(nums,0));
	}
}
